package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension.more;

// 不同的子序列
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences/
public class Code01_DistinctSubsequences {

    public static void main(String[] args) {
        Code01_DistinctSubsequences  test = new Code01_DistinctSubsequences();
        System.out.println(test.numDistinct("rabbbit", "rabbit"));
    }


    public int numDistinct(String s, String t) {
//        int[][] dp = new int[s.length()+1][t.length()+1];
//        return f2(s.toCharArray(),t.toCharArray(),s.length(),t.length(),dp);
        //return f1(s.toCharArray(),t.toCharArray(),s.length()-1,t.length()-1);
        //return f3(s.toCharArray(),t.toCharArray());
        return f4MySelf(s.toCharArray(),t.toCharArray());

    }


    private int f4MySelf(char[] s, char[] t) {
        int[] dp = new int[t.length+1];
        int sLen = s.length;
        int tLen = t.length;
        for (int i = 1; i <= sLen; i++) {
            dp[0] = 1;
            int leftUp =1;
            for (int j = 1; j <= tLen; j++) {
                int tmp = dp[j];
                if (s[i - 1] == t[j - 1]) {
                    dp[j] += leftUp;
                }
                leftUp = tmp;
            }
        }
        return dp[t.length];
    }

    private int f4MySelf2(char[] s, char[] t) {
        int[] dp = new int[t.length+1];
        int sLen = s.length;
        int tLen = t.length;
        for (int i = 1; i <= sLen; i++) {
            dp[0] = 1;
            int leftUp =1;
            for (int j = 1; j <= tLen; j++) {
                int tmp = dp[j];
                if (s[i - 1] == t[j - 1]) {
                    dp[j] += leftUp;
                }
                leftUp = tmp;
            }
        }
        return dp[t.length];
    }


    /**
     * @param s
     * @param t
     * @return
     */
    private int f4(char[] s, char[] t) {
        int n = s.length;
        int m = t.length;
        int[] dp = new int[m + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (s[i - 1] == t[j - 1]) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[m];
    }


    private int f3(char[] s, char[] t) {
        int[][] dp = new int[s.length+1][t.length+1];
        int sLen = s.length;
        int tLen = t.length;
        for (int i = 0; i <= sLen; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i <= tLen; i++) {
            dp[0][i] = 0;
        }

        for (int i = 1; i <=sLen; i++) {
            for (int j = 1; j <= tLen; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[sLen][tLen];
    }

    /**
     * 根据长度处理
     * @param s
     * @param t
     * @param i
     * @param j
     * @param dp
     * @return
     */
    private int f2(char[] s, char[] t, int i, int j, int[][] dp) {
        //base case
        if(j==0){
            dp[i][j] = 1;
            return 1;
        }
        if(i==0){
            dp[i][j] = 0;
            return 0;
        }
        if(dp[i][j]!=0){
            return dp[i][j];
        }
        int ans =0;
        if(s[i-1]==t[j-1]){
            int a = f2(s,t,i-1,j-1,dp);
            int b = f2(s,t,i-1,j,dp);
            ans+=a+b;
        }else{
            ans+=f2(s,t,i-1,j,dp);
        }
        dp[i][j] = ans;
        return ans;
    }


    /**
     * 可能性分析
     * 从后到前
     * s以为 i位置结尾
     * 当前i位置与j位子字符不一致 ：  找f1（i-1,j）
     *                  一致 ：  a：当前位置要 f1（i-1,j-1）  b：当前位置不要f1(i-1,j)
     * @param s
     * @param t
     * @param i
     * @param j
     * @return
     */
    private int f1(char[] s, char[] t, int i, int j) {
        //base case
        if(j<0){
            return 1;
        }
        if(i<0){
            return 0;
        }
        int ans =0;
        if(s[i]==t[j]){
              int a = f1(s,t,i-1,j-1);
              int b = f1(s,t,i-1,j);
              ans+=a+b;
        }else{
            ans+=f1(s,t,i-1,j);
        }
        return ans;
    }

}
